//
// Description: 887. 求组合数 III
// Created by Loading on 2022/5/27.
//

/*
 * Lucas（卢卡斯）定理，若p是质数，则对于任意整数 1 <= m <= n，
 * 有：C(n, m) = C(n % p, m % p) * C(n / p, m / p) (mod p)
 */

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int p;

// 快速幂求逆元
int qmi(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) {
            res = (LL) res * a % p;
        }
        a = (LL) a * a % p;
        b >>= 1;
    }

    return res;
}

// 通过定理求组合数 C(a, b)
int C(int a, int b) {
    if (a < b) {
        return 0;
    }
    int res = 1;
    for (int i = a, j = 1; j <= b; --i, ++j) {
        res = (LL) res * i % p;
        res = (LL) res * qmi(j, p - 2) % p;
    }

    return res;
}

// lucas定理函数
int lucas(LL a, LL b) {
    if (a < p && b < p) {
        return C(a, b);
    }
    return (LL) C(a % p, b % p) * lucas(a / p, b / p) % p;
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        LL a, b;
        cin >> a >> b >> p;

        int res = lucas(a, b);

        cout << res << endl;
    }

    return 0;
}